루프

입력 값은 항상 n 이라고 표기한다.

for(i=1;i<=n;i++){
	m += 2;
}

여기서 m에 2씩 더해주는 계산을 c라고 하면
n번 만큼 c계산이 실행되는것이니까 c*n 의 복잡도.
그런데 c와 같은 상수들은 제외하고 표기하니까 O(n)의 복잡도

중복 루프

for(i=1;i<=n;i++){
	for(j=1;j<=n;j++){
    	k += 2;
    }
}

여기서는 n번을 반복하는데 각 반복마다 n번씩 반복문을 실행하니
(c∗n)∗n=n2 그래서 O(n2)의 복잡도라고 표기

if-then-else

if(length()==0){
	return false; // c0
}else{
	... // c1
	for(i=0;i<length();i++){
    	... // c2
    	if(){
        	... // c3
        }
    }
}

if를 f(n), else를 g(n)이라고 하고
**max(f(n),g(n))**을 구하면 제일 높은 복잡도를 가진 경우를 구할 수 있는데
이걸 f(n)+g(n) 이라고 표현한다고.
만약 f(n)이 n4, g(n)이 n3라면 n4+n3이 되고
작은게 사라지니까 O(n4)만 남는다.

위의 예시를 보면 c0​+c1​+n(c2​+c3​) 고 상수를 제거하면 O(n)의 복잡도.

로그형 복잡도

어떤 알고리즘의 문제의 크기를 일부 줄이는데 일정한 시간이 걸린다면 O(logn)

for(i=1;i<=n;){
	i = i*2;
}

위의 코드를 보면 i++이 아니라 2씩 곱해주고 있다.
만약 n이 1000이라면 i는 1,2,4,8,16,32,64,128,256,512,1028, ... 로 진행되는데 거기서 i<1000을 만족하는 512까지 반복 횟수는 10이다.
곱하기 2씩 해주니까 반복회수가 k라면 i=2k인것.
그래서 log2​가 되고 n은 입력의 수니까 log2​1000

예시) 이진 검색 - 사전(n페이지)에서 단어 찾기

n개의 자료가 있을때 트리 자료형에 관리를 해둔다면?
예를들어 81라는 숫자가 트리에 있는지 확인하려면, 기존 배열에서는 최악의 경우 배열의 처음부터 끝까지 즉 n번 연산을 실행해야 한다.
그런데 트리형에서는 트리의 높이만큼만 확인해보면 81이 있는지 없는지 알 수 있다.
트리의 높이는 n<2k 로 계산된다. 즉 만약 14개의 숫자가 있다고 하면 k는 4고 트리의 높이는 4층. 최대 4번 확인해보면 된다. (잘 정렬되어있다면)
만약 사전에 단어가 2만개가 있다고 가정하면 n=20000이고 이걸 log를 하면 14.3이 나오고 트리의 높이는 15층.

재귀recursion란 무엇인가?

자기 자신을 호출하는 함수.
자기 자신의 복사본을 호출하여 더 작은 문제를 풀게 하여 문제를 해결한다.
작은 문제의 서열은 결국 기본 경우 base case로 수렴해야 한다.

수학적 귀납법에서
n=1을 증명하고,
n=i를 가정해서 n=i+1을 증명하면
성공적으로 증명을 한다고 했다.
재귀도 이것과 비슷하다.

예시) 팩토리얼

n!=1∗2∗3∗....∗n
이건 다시 n!=n∗(n−1)!과 같다.
이걸 재귀함수로 만들면

int Fact(int n){
	if(n==1){ //base case
    	return 1;
    }else if(n==0){ //base case
    	return 1;
    }else{ //recursion step  
     	return n*Fact(n-1); //더 작아진다.
    }
}

27이 입력된다면 기본경우에 해당되지 않으니까 27*Fact(26)을 반환하는데 이건 다시 26*Fact(25)가 되고 ...... 반복.
이 경우에는 for반복문이 훨씬 직관적이고 편하긴 하다.

재귀 알고리즘은 위에서처럼 재귀적 경우 recursion step과 기본 경우 base case 두 가지로 나뉘고. 기본 경우에 종료된다.

재귀와 메모리

int Print(int n){
	if(n==0){
    	return 0;
    }else{
    	printf("%d",n);
        return Print(n-1);
    }
}

n=5라면 5,4,3,2,1을 출력한다.
그런데 실제로 보면 기본경우에서 반환하는 0은 역순으로 쭉 타고 올라온다.
출력->(재귀함수)호출->출력->호출->....-> 0 기본경우에 도착하면
반환되는 0은 Print(1)로 올라가고 Print(1)은 Print(2)로 0을 반환하고 이렇게 처음 Print(5)까지 올라가서 마지막으로 0을 반환하고 종료.

그러니까 스택에 Print(5)가 올라가고 그 위에 Print(4)가 올라가고 3,2,1,0 까지 올라갔다가 0,1,2 순서대로 하나씩 사라진다(각 한칸식을 '스택 프레임'이라고 한다). 즉 메모리 추가 공간이 필요하다는 말.
그래서 일반적으로 for반복문이 효율적이다. 하지만 재귀를 사용해야되는 많은 경우 눈에 띄는 반복적 알고리즘이 없을 수 있고 그렇다면 재귀 알고리즘을 사용.